"""
 ① 找到待排序列表中的最大值 k，开辟一个长度为 k+1 的计数列表，计数列表中的值都为 0。
 ② 遍历待排序列表，如果遍历到的元素值为 i，则计数列表中索引 i 的值加1。
 ③ 遍历完整个待排序列表，计数列表中索引 i 的值 j 表示 i 的个数为 j，统计出待排序列表中每个值的数量。
 ④ 创建一个新列表（也可以清空原列表，在原列表中添加），遍历计数列表，依次在新列表中添加 j 个 i，新列表就是排好序后的列表，整个过程没有比较待排序列表中的数据大小
O(1) < O(logn) < O(n) < O(nlogn) ....< O(n^2) < O(n!)
"""


# 计数器排序


def count_sort(sort_list):
    # 如果集合长度小于2 直接返回
    if len(sort_list) < 2:
        return sort_list
    # 找到最大的元素
    max_num = max(sort_list)
    # 构建一个定长计数列表
    count_list = [0 for x in range(max_num + 1)]
    # 把原列表值按照新的排序放入进去
    for a in sort_list:
        count_list[a] += 1
    # 清空原来的数组
    sort_list.clear()
    for index, count in enumerate(count_list):
        # count 在原来数组的值 index应该排在第几位
        for val in range(count):
            sort_list.append(index)
    return sort_list


'''
    ① 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
    ② 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
    ③ 针对所有的元素重复步骤 ① ~ ②，除了最后一个元素，直到排序完成。
'''


def bubble_sort_1(sort_list):
    for i in range(len(sort_list) - 1):
        # 跟索引大于自己的比较
        for j in range(len(sort_list) - i - 1):
            # 如果这个数大于后面的数就交换两者的位置
            if sort_list[j + 1] < sort_list[j]:
                temp = sort_list[j]
                sort_list[j + 1] = sort_list[j]
                sort_list[j] = temp
                # print(sort_list)
    return sort_list


def bubble_sort_2(sort_list):
    for i in range(len(sort_list) - 1):
        # 在这里建立一个标识 如果下一个有序则直接跳过交换
        flag = False
        for j in range(len(sort_list) - i - 1):
            # 如果这个数大于后面的数就交换两者的位置
            if sort_list[j + 1] < sort_list[j]:
                temp = sort_list[j]
                sort_list[j + 1] = sort_list[j]
                sort_list[j] = temp
                flag = True
                # print(sort_list)
        if not flag:
            return sort_list
    return sort_list


'''
    ① 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
    ② 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
    ③ 重复步骤 ②，直到所有元素均排序完毕。
'''


def select_sort(sort_list):
    for i in range(len(sort_list) - 1):
        # 保存最小的元素的下标
        min_index = i
        # 如果这个数小于记录的最小数，则更新最小数的下标
        for j in range(i + 1, len(sort_list)):
            if arr[j] < arr[min_index]:
                min_index = j
        # 进行交换
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return sort_list


# 桶排序又叫箱排序，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。
#
# 桶排序也是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
#
# 在额外空间充足的情况下，尽量增大桶的数量；
# 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。
# 同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
#
# 最快情况：当输入的数据可以均匀的分配到每一个桶中；
# 最慢情况：当输入的数据被分配到了同一个桶中。
# 步骤
#
# ① 创建一个定量的数组当作空桶子；
# ② 遍历序列，把元素一个一个放到对应的桶子去；
# ③ 对每个不是空的桶子进行排序；


def bucket_sort(arr_list):
    # 1.创建n个空桶
    n = len(arr_list) // 2
    new_list = [[] for _ in range(n)]

    # 2.把arr[i] 插入到bucket[n*array[i]]
    for data in arr_list:
        index = int(data % n)
        new_list[index].append(data)

    # 3.桶内排序
    for i in range(n):
        new_list[i].sort()

    # 4.产生新的排序后的列表
    index = 0
    for i in range(n):
        for j in range(len(new_list[i])):
            arr_list[index] = new_list[i][j]
            index += 1
    return arr_list


arr = [2, 3, 8, 7, 1, 2, 2, 2, 5, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]
# print("count_sort", count_sort(arr))
print("bubble_sort_1", bubble_sort_1(arr))
# print("----------------------------------")
# print("bubble_sort_1", bubble_sort_1(arr))
# print("bucket_sort", bucket_sort(arr))
